package leetcode;


import java.util.*;

public class Code15 {
    public static void main(String[] args) {
        List<List<Integer>> lists = new Code15().threeSum2(new int[]{
                -4,0,-1,1,-1,2
        });
        for (List<Integer> list:lists){
            for (Integer a:list){
                System.out.print(a);
            }
            System.out.println();
        }
    }

    public List<List<Integer>> threeSum2(int[] nums) {
        HashMap<Integer,Integer> hashMap = new HashMap<>();
        Arrays.sort(nums);
        List<List<Integer>> lists = new ArrayList<>();
        for (int a=0;a<nums.length;a++){
            hashMap.put(nums[a],a);
        }
        for(int a=0;a<nums.length;a++){
            if (a>0&&nums[a]==nums[a-1]){
                continue;
            }
            for (int b=a+1;b<nums.length;b++){
                if (b>a+1&&nums[b]==nums[b-1]){
                    continue;
                }
                int end = 0-(nums[a]+nums[b]);
                if (hashMap.get(end)!=null&&hashMap.get(end)>b){
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[a]);
                    list.add(nums[b]);
                    list.add(0-(nums[a]+nums[b]));
                    lists.add(list);
                }
            }
        }
        return lists;
    }
}
